/********************************************
 *       Fichier fonctions de graphes       *
 *                graphes.c                 *
 *                                          *
 *     Grivolet Alenda Bourgeois Ciabaud    *
 ********************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "structures.h"

/* Initialise le graphe G */
void initGraphe( Graphe *G ){

	int i;

	G->nbSommets = 0;

	for( i=0; i<SOMMETS_MAX; i++ ){

		G->Sommets[i] = NULL;

	}

}

/* Libere la mémoire utilisée par la liste de G */
void freeGraphe( Graphe G ){

	Maillon *I, *prec;
	int i;

	/* Pour chaque sommet de G */
	for( i=0; i<G.nbSommets; i++ ){

		prec = NULL;

		/* Pour chaque voisin de G[i] */
		FOREACH(I,G.Sommets[i]){

			/* On libere l'élément précédent */
			if(prec!=NULL)
				free(prec);

			prec = I;

		}
		free(prec);

	}

}

/* Charge un graphe depuis l'entrée standard
 *
 * La syntaxe de l'entrée doit etre:
 * <Nombre de sommets> <Nombre d'aretes>
 * <Sommet 1> <Voisin 1>
 * <Sommet 1> <Voisin 2>
 * ...
 * <Sommet n>: <Voisin m>
 *
 * Un sommet est numerote de 0 a <Nombre de sommets-1>
 */
void chargerGraphe( Graphe *G, int affichage ){

	int i, s, v;

	/* Nombre de sommets */
	if(affichage) printf("\nNombre de sommets: ");
	scanf("%i", &(G->nbSommets));
	getchar();

	/* Nombre de sommets */
	if(affichage) printf("\nNombre d'aretes: ");
	scanf("%i", &(G->nbAretes));
	getchar();

	if(affichage) printf("\n");
	printf("Creation d'un graphe de %i sommets et de %i aretes\n", G->nbSommets, G->nbAretes);
	if(affichage) printf("Syntaxe: <Sommet i> <Voisin j>\n");

	/* Sommets */
	for( i=0; i<G->nbAretes; i++ ){

		/* Sommet étudié */
		scanf( "%i %i", &s, &v );

		/* Si le sommet n'existe pas */
		if(s<0||s>G->nbSommets-1||v<0||v>G->nbSommets-1){
			ERREUR("Sommet %i en dehors de la liste", s);
			exit(0);
		}

		/* On l'ajoute au Sommet */
		creerVoisin( G, s, v );
		creerVoisin( G, v, s );

	}
}

/* Ajoute le voisin au sommet dans G */
void creerVoisin( Graphe *G, int S, int V ){

	Maillon *I;

	/* Création du voisin */
	I = calloc( 1, sizeof(Maillon) );
	I->elt = V;
	I->suivant = NULL;

	/* Si c'est le premier element */
	if( G->Sommets[S] == NULL ){

		G->Sommets[S] = I;

	}else{

		I->suivant = G->Sommets[S];
		G->Sommets[S] = I;

	}

}

/* Affiche le graphe */
void afficherGraphe( Graphe G ){

	int s;
	Maillon *I;

	printf("Graphe de %i sommets:\n", G.nbSommets );

	/* Pour chaque sommet */
	for(s=0;s<G.nbSommets;s++){

		printf("Sommet %i: ", s+1);

		FOREACH(I,G.Sommets[s])
			printf("%i ", I->elt+1);

		printf("\n");

	}

}

